#include<iostream>
#include<algorithm>

using namespace std;
int n;


int oula(int x)
{
	if(x<2) return 1;
	
	int sum=x;
	for(int i=2;i<=x/i;i++){
		if(x%i==0){
			sum=sum/i*(i-1);
			while(x%i==0) x/=i;
		}
	}
	if(x>1) sum=sum/x*(x-1);
	
	return sum;
}


int main()
{
	cin>>n;
	
	while(n--){
		int x;
		cin>>x;
		printf("%d\n",oula(x));
	}
	
	return 0;
}
